#include "Heap.h"


void Swap(int* p1, int* p2)
{
	assert(p1 && p2);
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下调整
void AdjustDown(HPDataType* arr, int parent, int size)
{
	assert(arr);
	//假设左孩子为最小值
	int child = parent * 2 + 1;
	while (child < size)
	{
		//防止越界访问堆并将左孩子与右孩子进行比较
		if (child + 1 < size && arr[child + 1] < arr[child])
			child++;
		//孩子比父亲小
		if (arr[child] < arr[parent])
		{
			//进行交换
			Swap(&arr[child], &arr[parent]);
			//将原目标节点的父节点当作新的父节点
			parent = child;
			//寻找新的父节点的左孩子节点
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

//向上调整
void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);
	//找父亲
	int parent = (child - 1) / 2;
	while( child > 0)
	{
		//孩子比父亲小,则进行交换
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			//原目标节点的父节点当作新的目标节点
			child = parent;
			//寻找新的目标节点的父节点
			parent = (child - 1) / 2;
		}
		//调整完成,已成堆
		else
		{
			break;
		}

	}
}

//插入
void HeadPush(Heap* pile, HPDataType value)
{
	//插入之前先检查容量
	if (pile->capcity == pile->size)
	{
		int newcapacity = pile->capcity == 0 ? 4 : pile->capcity * 2;
		//进行扩容
		HPDataType* Tmp = (HPDataType*)realloc(pile->arr, newcapacity * sizeof(HPDataType));
		if (Tmp == NULL)
		{
			perror("malloc fail");
			return;
		}
		pile->arr = Tmp;
		pile->capcity = newcapacity;
		//插入数据
		pile->arr[pile->size] = value;
	
		//进行向上调整
		AdjustUp(pile->arr, pile->size);
		pile->size++;
	}
}


//规定删除根节点
void HeapPop(Heap* pile)
{
	assert(pile);
	//首尾交换
	Swap(&pile->arr[0], &pile->arr[pile->size - 1]);
	pile->size--;
	//进行向下调整
	AdjustDown(pile->arr, 0, pile->size);
}

//初始化堆
void HeapInit(Heap* pile)
{
	assert(pile);
	pile->arr = NULL;
	pile->capcity = pile->capcity = 0;
}

//建立堆
void HeapCreate(Heap* pile, HPDataType* arr, int size)
{
	assert(pile && arr);
	HPDataType* Tmp = (HPDataType*)malloc(sizeof(HPDataType) * size);
	if (Tmp == NULL)
	{
		perror("malloc fail");
		return ;
	}
	pile->arr = Tmp;
	pile->capcity = pile->size = size;
	//拷贝数据
	memcpy(pile->arr, arr, sizeof(HPDataType) * size);
	//从倒数第一个非叶子节点开始进行向下调整
	for (int i = (size - 1 - 1) / 2; i >= 0 ; i--)
	{
		AdjustDown(pile->arr, i, size);
	}
}

//获取堆顶元素
HPDataType HeadTop(Heap* pile)
{
	return pile->arr[0];
}


//获取堆的元素个数
int HeapSize(Heap* pile)
{
	return pile->size;
}

//堆是否为空
bool HeapEmpty(Heap* pile)
{
	return pile->size == 0 ? true : false;
}

//销毁堆
void HeapDestory(Heap* pile)
{
	free(pile->arr);
	pile->arr = NULL;
	pile->capcity = 0;
	pile->size = 0;
}


